package com.study.lu.动态规划;

public class 打家劫舍2_1 {
    /**
     * 居于 打家劫舍 的基础上，第一间房子和最后一间房子是相连的.
     * 如果偷了第一家，那么最后一家不能偷， 如果没偷第一家。最后一家是可以偷的
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 1};
        int n = rob(nums);
        System.out.println(n);
    }

    private static int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(doRob(0, nums, length - 2), doRob(1, nums, length - 1));

    }

    private static int doRob(int start, int[] nums, int end) {
        int first = nums[start];
        int second = Math.max(nums[start], nums[start + 1]);
        int temp=0;
        for (int i = start + 2; i <= end; i++) {
            temp = second;
            second = Math.max(second, first + nums[i]);
            first = temp;
        }

        return second;

    }
}
